package utils.opt;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;

import option.KBVocabulary;

import utils.Util;
import utils.exception.CacheNodeException;

import entities.Individual;
import entities.concept.AndConcept;
import entities.concept.Concept;
import entities.concept.DomainConceptEQ;
import entities.concept.ExistsConcept;
import entities.role.Role;
import entities.role.GeneralRolePath;

/**
 * A cache tree is a tree with degree 2. Every node contains a binary map that
 * maps to: either 1. Special role RID to some concept or 2. some feature to
 * values
 * 
 * IMPORTANT: a cache tree is only safe for a particular KB. Use caution when
 * deploy the app on a server, where many KBs have identical instance names.
 * 
 * @author j55wu
 * 
 */
public class CacheTree {
	private static HashMap<Individual, CacheTree> cache = new HashMap<Individual, CacheTree>();
	private final Individual ind;
	// each root leads a path of nodes (linked list), head has no incoming links
	private HashSet<CacheTreeNode> roots;
	public static boolean UNSOUND_CACHE = true;

	public static void addCache(Individual ind, GeneralRolePath grp, Concept con) {
		CacheTree tree = null;
		if (cache.containsKey(ind)) {
			tree = cache.get(ind);
		} else {
			tree = new CacheTree(ind);
		}
		try {
			tree.insertCacheEntry(ind, grp, con);
		} catch (CacheNodeException e) {
			System.out.println("Cache entry not inserted: " + grp + con);
		}
		cache.put(ind, tree);
	}

	public static HashSet<String> findCacheForFeature(Individual ind,
			GeneralRolePath grp, Role f) {
		HashSet<String> ks = new HashSet<String>();
		if (cache.containsKey(ind)) {
			CacheTree ctree = cache.get(ind);
			if (grp == null || !grp.hasRoles()) {
				// top level role path
				for (CacheTreeNode nd : ctree.roots) {
					if (nd.getKVMap() != null && nd.getKVMap().containsKey(f)) {
						for (Object o : nd.getKVMap().get(f)) {
							ks.add((String) o);
						}
					}
				}
				return ks;
			}
			ks.addAll(findCacheForFeature(ctree, grp, f));
			// System.err.println("cahce found "+f+", possible values:"+ks.size());
		}
		return ks;
	}

	private static HashSet<String> findCacheForFeature(CacheTree ctree,
			GeneralRolePath rp, Role f) {
		HashSet<String> ks = new HashSet<String>();
		for (CacheTreeNode nd : ctree.roots) {
			ks.addAll(findCacheForFeature(nd, rp, f));
		}
		return ks;
	}

	private static HashSet<String> findCacheForFeature(CacheTreeNode nd,
			GeneralRolePath grp, Role f) {
		HashSet<String> ks = new HashSet<String>();
		if (!grp.hasRoles()) {
			if (UNSOUND_CACHE) {
				// any possible values are returned
				if (nd.getKVMap().containsKey(f)) {
					for (Object o : nd.getKVMap().get(f)) {
						ks.add((String) o);
					}
				}
			}
			return ks;
		}
		GeneralRolePath myrp = grp.newCopy();
		CacheTreeNode next = nd.getNextNode(myrp.getLastRole());
		if (next != null) {
			// remove this role and continue on the next one
			if (UNSOUND_CACHE) {
				int rindex = myrp.getLastRoleIndex();
				// Concept rmc = myrp.removeContentToBottom(rindex);
				myrp.removeContentToBottom(rindex);
			}

			ks.addAll(findCacheForFeature(next, myrp, f));
		}
		return ks;
	}

	public CacheTree(Individual ind) {
		this.ind = ind;
		this.roots = new HashSet<CacheTreeNode>();
	}

	public HashSet<CacheTreeNode> getRoots() {
		return this.roots;
	}

	public void insertCacheEntry(Individual ins, GeneralRolePath rp, Concept c)
			throws CacheNodeException {
		if (!ins.equals(ind)) {
			throw new CacheNodeException("The instance does not match...");
		}
		if (rp == null || !rp.hasRoles()) {
			CacheTreeNode head = new CacheTreeNode(null, null, null,
					new HashMap<Role, HashSet<Object>>());
			// no roles, just add the concept TODO: what if rp.concept is not
			// null??
			head.addNodeValue(Util.parseConceptFromGeneralRolePath(rp, c));
			this.roots.add(head);
		} else {
			CacheTreeNode head = samePathFoundFromRoot(rp);
			if (head == null) {
				head = new CacheTreeNode(null, null, null, null);
				this.insertCacheEntry(head, rp, c);
				this.roots.add(head);
			} else {
				modifyExistingPath(head, rp, c);
			}
		}

	}

	// modify a path that share some prefixing roles
	public void modifyExistingPath(CacheTreeNode head, GeneralRolePath rp,
			Concept c) throws CacheNodeException {
		if (rp.length() <= 0) {
			this.insertCacheEntry(head, rp, c);
			if (head.getIncomingRole() == null) {
				this.roots.add(head);
			}
			return;
		}
		GeneralRolePath myrp = rp.newCopy();
		Role r = myrp.getOldestRole();
		if (head.hasNextNode(r)) {
			// if any concept belongs to the current node
			Concept gen = myrp.removeContentToIndex(myrp.getOldestRoleIndex());
			if (gen != null) {
				head.addNodeValue(gen);
			}
			if (head.getNextNode1().getIncomingRole().equals(r)) {
				modifyExistingPath(head.getNextNode1(), myrp, c);
			} else if (head.getNextNode2().getIncomingRole().equals(r)) {
				modifyExistingPath(head.getNextNode2(), myrp, c);
			} else {
				throw new CacheNodeException("No path found for this role:" + r);
			}
		} else {
			this.insertCacheEntry(head, myrp, c);
			if (head.getIncomingRole() == null) {
				this.roots.add(head);
			}
		}

	}

	// test if the most recent role (not necessarily the bottom one) is seen on
	// some path
	public CacheTreeNode samePathFoundFromRoot(GeneralRolePath rp)
			throws CacheNodeException {
		Role r = rp.getOldestRole();
		for (CacheTreeNode nd : this.roots) {
			if (nd.hasNextNode(r)) {
				return nd;
			}
		}
		return null;
	}

	private void insertCacheEntry(CacheTreeNode start, GeneralRolePath rp,
			Concept c) throws CacheNodeException {
		Concept ec = utils.Util.parseConceptFromGeneralRolePath(rp, c);
		// add roles in sequence
		start.addNodeValue(ec);
	}

}

/**
 * A node has two pointers, as said above. A node value can be: Id->concepts; or
 * F->Strings; or null; Null value means this node has subnodes. Leaf nodes are
 * concept nodes, while intermediate nodes are null nodes.
 * 
 * @author j55wu
 * 
 */
class CacheTreeNode {
	// at most two next nodes: some R.C and some S.D
	private CacheTreeNode nextNode1;
	private CacheTreeNode nextNode2;
	private final Role incomeRole;
	private HashMap<Role, HashSet<Object>> nodemap;

	public CacheTreeNode(CacheTreeNode next1, CacheTreeNode next2, Role link,
			HashMap<Role, HashSet<Object>> values) {
		this.nextNode1 = next1;
		this.nextNode2 = next2;
		this.incomeRole = link;
		this.nodemap = values;
	}

	public Role getIncomingRole() {
		return this.incomeRole;
	}

	public CacheTreeNode getNextNode1() {
		return this.nextNode1;
	}

	public CacheTreeNode getNextNode2() {
		return this.nextNode2;
	}

	// a leaf node has only a map of value, no pointers
	public static CacheTreeNode newLeafCacheTreeNode(Role link) {
		return new CacheTreeNode(null, null, link,
				new HashMap<Role, HashSet<Object>>());
	}

	public void setNextNode1(CacheTreeNode next) {
		this.nextNode1 = next;
	}

	public void setNextNode2(CacheTreeNode next) {
		this.nextNode2 = next;
	}

	public void addNodeValue(Concept c) throws CacheNodeException {
		if (c instanceof DomainConceptEQ<?, ?>) {
			DomainConceptEQ<?, ?> dc = (DomainConceptEQ<?, ?>) c;
			Role f = (Role) dc.getRealFeature();
			String k = (String) dc.getRealValue();
			this.addToNodeMap(f, k);
		} else if (c instanceof AndConcept) {
			// add as ID -> C, decomposing AndConcepts as well
			if (!CacheTree.UNSOUND_CACHE) {
				this.addToNodeMap(KBVocabulary.ROLE_ID, c);
			}
			for (Concept ac : ((AndConcept) c).getConceptSet()) {
				this.addNodeValue(ac);
			}
		} else if (c instanceof ExistsConcept) {
			ExistsConcept ec = (ExistsConcept) c;
			Role er = ec.getRole();
			this.addExistsNodeValue(this, er, ec.getFiller());

		} else {
			this.addToNodeMap(KBVocabulary.ROLE_ID, c);
		}
	}

	public CacheTreeNode addExistsNodeValue(CacheTreeNode father, Role r,
			Concept c) throws CacheNodeException {
		CacheTreeNode ret = null;
		if (!father.hasNextNode(r)) {
			// create new node
			CacheTreeNode nd = new CacheTreeNode(null, null, r,
					new HashMap<Role, HashSet<Object>>());
			nd.addNodeValue(c);
			ret = nd;
			if (father.nextNode1 == null) {
				father.nextNode1 = nd;
			} else if (father.nextNode2 == null) {
				father.nextNode2 = nd;
			} else {
				throw new CacheNodeException(
						"Unable to have three subnodes for this concept: " + c);
			}
		} else if (father.nextNode1 != null
				&& father.nextNode1.incomeRole.equals(r)) {
			ret = father.nextNode1;
			father.nextNode1.addNodeValue(c);
		} else if (father.nextNode2 != null
				&& father.nextNode2.incomeRole.equals(r)) {
			ret = father.nextNode2;
			father.nextNode2.addNodeValue(c);
		} else {
			throw new CacheNodeException(
					"Both subnodes have this role as label: " + r);
		}
		return ret;
	}

	public boolean hasNextNode(Role r) throws CacheNodeException {
		if (this.nextNode1 != null && this.nextNode1.incomeRole.equals(r)) {
			// already had this role
			return true;
		} else if (this.nextNode2 != null
				&& this.nextNode2.incomeRole.equals(r)) {
			return true;
		}
		return false;
	}

	public HashMap<Role, HashSet<Object>> getKVMap() {
		return this.nodemap;
	}

	public CacheTreeNode getNextNode(Role r) {
		if (this.nextNode1 != null && this.nextNode1.incomeRole.equals(r)) {
			return this.nextNode1;
		} else if (this.nextNode2 != null
				&& this.nextNode2.incomeRole.equals(r)) {
			return this.nextNode2;
		}
		return null;
	}

	// add: ID -> C or f->k
	private void addToNodeMap(Role r, Object o) {
		if (this.nodemap == null) {
			this.nodemap = new HashMap<Role, HashSet<Object>>();
		}
		HashSet<Object> values = null;
		if (this.nodemap.containsKey(r)) {
			values = this.nodemap.get(r);
		} else {
			values = new HashSet<Object>();
		}
		if (o != null && o instanceof Concept) {
			values.add((Concept) o);
		} else if (o != null && o instanceof String) {
			values.add((String) o);
		}
		this.nodemap.put(r, values);
	}

	public static String displayTree(CacheTreeNode head, int i) {
		String out = "";
		for (int j = i; j > 0; j--) {
			out += "--";
		}
		if (head.getIncomingRole() != null) {
			out += head.getIncomingRole() + "***";
		} else {
			out += "HEAD\n";
		}
		i++;
		if (head.nodemap != null) {
			for (Entry<Role, HashSet<Object>> e : head.nodemap.entrySet()) {
				out += e.getKey().toString() + "->(";
				for (Object o : e.getValue()) {
					out += o.toString() + ",";
				}
				out += "); ";
			}
			out += "\n";
		}

		if (head.getNextNode1() != null) {
			out += "L: " + displayTree(head.getNextNode1(), i);
		}
		if (head.getNextNode2() != null) {
			out += "R: " + displayTree(head.getNextNode2(), i);
		}
		return out;
	}

	@Override
	public String toString() {
		String st = this.hashCode() + ": ";
		st += " <--- " + this.incomeRole + ".{";
		if (this.nodemap == null) {
			st += "}";
		} else {
			for (Entry<Role, HashSet<Object>> e : this.nodemap.entrySet()) {
				st += e.getKey().toString() + "->(";
				for (Object o : e.getValue()) {
					st += o.toString() + ",";
				}
				st += "); ";
			}
			st += "}";
		}

		// if(this.nextNode1 != null){
		// st+="\n"+ this.hashCode() +" left -- " + this.nextNode1.toString();
		// }
		// if(this.nextNode2 != null){
		// st+="\n"+ this.hashCode() +" right -- " + this.nextNode2.toString();
		// }
		return st;
	}

}